package LeetCode刷题;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-09 11:07
 * @description: Functions of this class is
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 例：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 *
 **/
public class No全排列 {
    public static void main(String args[]){
        System.out.println(permute(new int[]{1,2,3}));
    }
    public static List<List<Integer>> permute(int[] nums) {
        //回溯算法
        List<Integer> sub=new ArrayList<>();
        List<List<Integer>>ans=new ArrayList<>();
        dfs(0,nums.length-1,nums,sub,ans);//从0开始递归
        return ans;

    }
    private static void dfs(int index,int right,int nums[],List<Integer> sub,List<List<Integer>>ans){
        if(index==right){//如果索引指针到达了右边界了

            sub=new ArrayList<>();//每次开辟一个集合，用于装新的全排列顺序
            for(int i=0;i<nums.length;i++){
                sub.add(nums[i]);
            }

            ans.add(sub);//将全排列顺序放入到答案集合中
            return;
        }

        //在index所指的位置到right的范围内去动态维护数组
        for(int i=index;i<=right;i++){
            swap(nums,index,i);//每次都进行交换，形成不同的
            dfs(index+1,right,nums,sub,ans);

            //在递归回退时，也要再进行一次交换*** 1 3 2-> 1 2 3
            swap(nums,index,i);
        }

    }
    public static void swap(int nums[],int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}